package edu.vt.ece.rt.benchmark.skiplist;

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.InputStream;
import java.io.ObjectInput;
import java.io.ObjectInputStream;
import java.io.ObjectOutput;
import java.io.ObjectOutputStream;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.Random;

import edu.vt.ece.rt.benchmark.BenchmarkThread;
import edu.vt.ece.rt.benchmark.counter.Counter;
import edu.vt.ece.rt.benchmark.intruder.Stream;
import edu.vt.ece.rt.benchmark.list.Benchmark;
import edu.vt.ece.rt.dstm.Context;
import edu.vt.ece.rt.dstm.ContextDelegator;
import edu.vt.ece.rt.dstm.QObject;
import edu.vt.ece.rt.dstm.TMProxy;
import edu.vt.ece.rt.quorum.ClustersManager;
import edu.vt.ece.rt.quorum.Resource;
import edu.vt.ece.rt.quorum.util.AbortException;
import edu.vt.ece.rt.quorum.util.Names;
import edu.vt.ece.rt.util.Logger.Logger;

public class SkipList extends QObject {

	public String[] Next ;
	public int Value;
	String id;
	
	
    public SkipList(String id, int value, int level)
    {
        Value = value;
        Next = new String[level];
        this.id = id;
		Resource.putQObject(getId(), this);
    }
    
    public SkipList(int value, int level)
    {
        Value = value;
        Next = new String[level];
    }
    

	@Override
	public QObject clone() {
		SkipList s = new SkipList(Value, Next.length);
		s.id = getId();
		s.setVersion(getVersion());
		s.setCloneOwner(getCloneOwner());
		s.Value = Value;
		for (int i = 0; i < Next.length; i++) {
			s.Next[i] = Next[i];
		}
		return s;
	}

	@Override
	public String getId() {
		return id;
	}
    
    
    
    public static SkipList head; // The max. number of levels is 33
    public static Random rand = new Random();
    public static int levels = 1;
	

    /* Inserts a value into the skip list. */
    public static void InsertInit(int value, ArrayList<Integer> arr)
    {
        // Determine the level of the new node. Generate a random number R. The number of
        // 1-bits before we encounter the first 0-bit is the level of the node. Since R is
        // 32-bit, the level can be at most 32.
        int level = 0;
        for (int R = arr.get(value); (R & 1) == 1; R >>= 1)
        {
            level++;
            if (level == levels) { levels++; break; }
        }

        SkipList newNode = new SkipList(Long.toString(value), value, level + 1);
        
        SkipList cur = (SkipList) Resource.getQObject("head");
        for (int i = levels - 1; i >= 0; i--)
        {
            for (; cur.Next[i] != null; cur = (SkipList) Resource.getQObject(cur.Next[i]))
            {
            	SkipList next = null;
            	if (cur.Next[i] != null) {
            		next = (SkipList) Resource.getQObject(cur.Next[i]);
            	}
                if (next != null && next.Value > value) break;
            }

            if (i <= level) { 
            	newNode.Next[i] = cur.Next[i]; cur.Next[i] = newNode.getId();
            }
        }        
    }

    
 
    /* Inserts a value into the skip list. */
    public static void Insert(int value, Context context) throws AbortException
    {

    	int level = getCurrLevel(context);
//    	System.out.println("level read/updated");
    	Logger.debug("level read/updated");

        int levels = ((SkipList) TMProxy.getTMProxy().read("levels", context.getContextId())).Value;
   	
//      System.out.println("level to be set is "+level);
        SkipList newNode = new SkipList( value, level + 1);
        Long newId = ContextDelegator.getNestedContext().getContextId();
        newNode.id = Long.toString(newId);
        newNode.setNewObject(true);
        context.addToCreateSet(newNode);
        
        SkipList cur = (SkipList) TMProxy.getTMProxy().read("head", context.getContextId());
        for (int i = levels - 1; i >= 0; i--)
        {
            for (; cur.Next[i] != null; cur = (SkipList) TMProxy.getTMProxy().read(cur.Next[i], context.getContextId()))
            {
            	SkipList next = null;
            	if (cur.Next[i] != null) {
            		next = (SkipList) TMProxy.getTMProxy().read(cur.Next[i], context.getContextId());
            	}
                if (next != null && next.Value > value) break;
            }

            cur = (SkipList) TMProxy.getTMProxy().write(cur.getId(), context.getContextId());
            if (i <= level) { 
//            	System.out.println("Setting the new node in skipList");
            	newNode.Next[i] = cur.Next[i]; cur.Next[i] = newNode.getId();
            }
        }        
//   	System.out.println("Insert completed for "+value);
   	Logger.debug("Insert completed for "+value);
    }
    
    
	public static void insert(int val, Context parentContext) throws AbortException {

		Long priority = System.currentTimeMillis();

		for (int i = 0; i < 0x7fffffff; i++) {

			((BenchmarkThread)Thread.currentThread()).collectStatsInner(i);
			Context context = ContextDelegator.getNestedContext();
			context.setParent(parentContext);
			context.setDescription("insert element in skiplist");
			context.sanityNested();
			context.setPriority(priority);

			Logger.debug("----Started----- R Transaction "+context.getContextId()+" on "+ClustersManager.baseClusterId);
			try {

				Insert(val, context);
				context.mergeParent();
				return;
				
			} catch (AbortException e) {
				if (e.getTransaction().longValue() != context.getContextId().longValue()) {
					Logger.debug("Exception in parent transaction "+e.getTransaction());
					//					System.out.println("Exception in parent transaction "+e.getTransaction());
					throw e;
				} else {
					Logger.debug("Exception in current transaction "+e.getTransaction());
					//					System.out.println("Exception in current transaction "+e.getTransaction());					
				}
			}
		}
		Logger.fetal("Unable to complete transaction in given number of tries");

		return;
	}

    public static int getCurrLevel(Context context) throws AbortException {
    	
        // Determine the level of the new node. Generate a random number R. The number of
        // 1-bits before we encounter the first 0-bit is the level of the node. Since R is
        // 32-bit, the level can be at most 32.
    	
        SkipList cur = (SkipList) TMProxy.getTMProxy().read("levels", context.getContextId());
        int level = 0;
        int levels = cur.Value;
        
        for (int R = rand.nextInt(); (R & 1) == 1; R >>= 1)
        {
            level++;
            if (level == levels) {
            	cur = (SkipList) TMProxy.getTMProxy().write("levels", context.getContextId());
            	cur.Value = new Integer(cur.Value + 1);
            	break;
            }
        }

        
        return level;

    }
	
    
    /* Returns whether a particular value already exists in the skip list */
    public static boolean Contains(int value, Context context) throws AbortException
    {
     	int level = getCurrLevel(context);
        int levels = ((SkipList) TMProxy.getTMProxy().read("levels", context.getContextId())).Value;
        
        SkipList cur = (SkipList) TMProxy.getTMProxy().read("head", context.getContextId());
        for (int i = levels - 1; i >= 0; i--)
        {
            for (; cur.Next[i] != null; cur = (SkipList) TMProxy.getTMProxy().read(cur.Next[i], context.getContextId()))
            {
            	SkipList next = null;
            	if (cur.Next[i] != null) {
            		next = (SkipList) TMProxy.getTMProxy().read(cur.Next[i], context.getContextId());
            	}

                if (next != null && next.Value > value) break;
                if (next != null && next.Value == value) return true;
            }
        }
        return false;
    }

    public static void write(int localObjectsCount, boolean nesting) {
		Context parentContext = null;
		Long priority = System.currentTimeMillis();
		Boolean delOp;
		
		ArrayList<Integer> arr = new ArrayList<Integer>();
		ArrayList<Boolean> booleanVal = new ArrayList<Boolean>();

		Random random = new Random();
		for (int j = 0; j < Integer.getInteger(Names.calls); j++ ) {
			arr.add(random.nextInt(localObjectsCount));

			if (random.nextInt(100) > 50) {
				booleanVal.add(true);
			} else {
				booleanVal.add(false);
			}

		}
		
		for (int i = 0; i < 0x7fffffff; i++) {

			((BenchmarkThread)Thread.currentThread()).collectStatsRoot(i);
			Context context = ContextDelegator.getNestedContext();
			context.setParent(parentContext);
			context.setDescription("starting root transaction");
			context.sanityNested();
			context.setPriority(priority);


			Logger.debug("----Started----- R Transaction "+context.getContextId()+" on "+ClustersManager.baseClusterId);
			try {

				for (int j = 0; j < arr.size();j++) {

					int val = arr.get(j);
					
					delOp = booleanVal.get(j);

					if (delOp) {
						Logger.debug("delete op with val " +val);
						if (nesting)
							remove(val, context);
						else
							Remove(val, context);
						
					} else {
						if (nesting)
							insert(val, context);
						else
							Insert(val, context);
					}
				}

				if (TMProxy.getTMProxy().requestCommit(context.getContextId())) {
					context.unsetParent(parentContext);
					return;
				}

			}  catch (AbortException e) {
				e.touch();
			}
		}
	
    }
    
    
	public static boolean contains(int val, Context parentContext) {

		Long priority = System.currentTimeMillis();
		boolean found = false;
		
		for (int i = 0; i < 0x7fffffff; i++) {

			((BenchmarkThread)Thread.currentThread()).collectStatsRoot(i);
			Context context = ContextDelegator.getNestedContext();
			context.setParent(parentContext);
			context.setDescription("insert element in skiplist");
			context.sanityNested();
			context.setPriority(priority);

			Logger.debug("----Started----- R Transaction "+context.getContextId()+" on "+ClustersManager.baseClusterId);
			try {

				found = Contains(val, context);
				
				if (TMProxy.getTMProxy().requestCommit(context.getContextId())) {
					context.unsetParent(parentContext);
					return found;
				}
			} catch (AbortException e) {
				Logger.debug("Aborting in loop "+context.getContextId());
				e.touch();
			}
		}
		Logger.fetal("Unable to complete transaction in given number of tries");

		return found;
	}
	
	
	
	
    /* Attempts to remove one occurence of a particular value from the skip list. Returns
    whether the value was found in the skip list. */
    
    public static boolean Remove(int value, Context context) throws AbortException
    {
//    	System.out.println("reading level");
    	Logger.debug("reading level");
        int levels = ((SkipList) TMProxy.getTMProxy().read("levels", context.getContextId())).Value;

        SkipList cur = (SkipList) TMProxy.getTMProxy().read("head", context.getContextId());

        boolean found = false;
        for (int i = levels - 1; i >= 0; i--)
        {
            for (; cur.Next[i] != null; cur = (SkipList) TMProxy.getTMProxy().read(cur.Next[i], context.getContextId()))
            {
              	SkipList next = null;
            	if (cur.Next[i] != null) {
            		next = (SkipList) TMProxy.getTMProxy().read(cur.Next[i], context.getContextId());
            	}
            	
                if (next != null && next.Value == value)
                {
                	next = (SkipList) TMProxy.getTMProxy().write(next.getId(), context.getContextId());
                	cur = (SkipList) TMProxy.getTMProxy().write(cur.getId(), context.getContextId());
                    found = true;
                    cur.Next[i] = next.Next[i];
                    break;
                }

                if (next != null && next.Value > value) break;
            }
        }
//    	System.out.println("Remove "+value+" completed");
    	Logger.debug("Remove "+value+" completed");
        return found;
    }

	public static boolean remove(int val, Context parentContext) throws AbortException {

		Long priority = System.currentTimeMillis();
		boolean found = false;
		
		for (int i = 0; i < 0x7fffffff; i++) {

			((BenchmarkThread)Thread.currentThread()).collectStatsInner(i);
			Context context = ContextDelegator.getNestedContext();
			context.setParent(parentContext);
			context.setDescription("remove element in skiplist");
			context.sanityNested();
			context.setPriority(priority);

			Logger.debug("----Started----- R Transaction "+context.getContextId()+" on "+ClustersManager.baseClusterId);
			try {

				found = Remove(val, context);
				context.mergeParent();
				return found;
				
			} catch (AbortException e) {
				if (e.getTransaction().longValue() != context.getContextId().longValue()) {
					Logger.debug("Exception in parent transaction "+e.getTransaction());
					//					System.out.println("Exception in parent transaction "+e.getTransaction());
					throw e;
				} else {
					Logger.debug("Exception in current transaction "+e.getTransaction());
					//					System.out.println("Exception in current transaction "+e.getTransaction());					
				}
				
			}
		}
		Logger.fetal("Unable to complete transaction in given number of tries");

		return found;
	}

    public static void main(String args[]) {
    	
    	ArrayList<Integer> arr = new ArrayList<Integer>(1000);
    	
    	for (int i = 0; i < 1000; i++) {
    		arr.add(rand.nextInt());
    	}
    	
    	try{
			OutputStream file = new FileOutputStream("random");
			OutputStream buffer = new BufferedOutputStream(file);
			ObjectOutput obj = new ObjectOutputStream(buffer);			
			obj.writeObject(arr);
			obj.close();
		
			InputStream file1 = new FileInputStream("random");
			InputStream buffer1 = new BufferedInputStream(file1);
			ObjectInput input1 = new ObjectInputStream(buffer1);

	    	ArrayList<Integer> arr1 = (ArrayList<Integer>)input1.readObject();
			System.out.println(arr1.size());
			
		} catch (Exception e) {
			
		}
		
    }

}
